package Calculation;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-10-08
 * Time: 16:18
 */

/*
* 四数之和*/
class Solution8 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList();
        Arrays.sort(nums);
        int n = nums.length;
        for(int i = 0 ; i < n ; ){
            //第一层循环遍历固定a遍历数组
            int a = nums[i];
            for(int j = i+1 ; j < n ; ){
                int b = nums[j] , left = j+1 ,right = n-1;
                long tem = (long)target - a - b;
                while(left < right){
                    long sum = sum(nums[left],nums[right]);
                    if(sum > tem){
                        right--;
                    }else if(sum < tem){
                        left++;
                    }else{
                        list.add(Arrays.asList(a,b,nums[left],nums[right]));
                        left++;
                        right--;
                        while(left < right && nums[left] == nums[left-1]){
                            left++;
                        }
                        while(right > left && nums[right] == nums[right+1]){
                            right--;
                        }
                    }
                }
                j++;
                while(j < n-2 && nums[j] == nums[j-1]){
                    j++;
                }
            }
            i++;
            while(i < n-1 && nums[i] == nums[i-1]){
                i++;
            }

        }
        return list;


    }
    public int sum(int a , int b){
        return a+b;

    }
}
public class Test8 {
    public static void main(String[] args) {
        Solution8 solution = new Solution8();
        int[] array = new int[]{1000000000,1000000000,1000000000,1000000000};
        solution.fourSum(array,-294967296);
    }

}
